package someTestExcemple.huaweiOd.unionFindSet;

import java.util.*;
//华为OD机试 - 工单调度策略 - 并查集（Java 2024 E卷 200分）
//https://blog.csdn.net/guorui_java/article/details/142664725

// 定义工单类
class WorkOrder {
    int slaTime;
    int score;

    public WorkOrder(int slaTime, int score) {
        this.slaTime = slaTime;
        this.score = score;
    }
}
//采用贪心算法结合优先队列（最小堆）来解决。
// 贪心算法的核心思想是在每一步都做出当前看起来最优的选择，最终得到全局最优解。
// 优先队列可以帮助我们高效地维护已选择工单的最小积分，方便我们进行替换操作。

public class WorkOrderScheduling {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取工单数量
        int n = scanner.nextInt();
        // 存储工单信息
        WorkOrder[] workOrders = new WorkOrder[n];
        for (int i = 0; i < n; i++) {
            int slaTime = scanner.nextInt();
            int score = scanner.nextInt();
            workOrders[i] = new WorkOrder(slaTime, score);
        }
        scanner.close();

        // 按照 SLA 时间对工单进行排序
        // 按照 SLA 时间从小到大排序，如果 SLA 时间相同，则按照积分从大到小排序
        Arrays.sort(workOrders, (a, b) -> {
            if (a.slaTime != b.slaTime) {
                return a.slaTime - b.slaTime;
            }
            return b.score - a.score;
        });

        // 使用优先队列（最小堆）存储已经选择的工单的积分
        //默认按照元素的自然顺序（对于 Integer 类型，就是数值从小到大的顺序）来维护队列，从而保证队首元素始终是最小的。
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int totalScore = 0;
        for (WorkOrder order : workOrders) {
            if (pq.size() < order.slaTime) { //因为每完成一个工单的时间都是1小时
                // 如果当前时间小于等于该工单的 SLA 时间，将该工单的积分加入优先队列
                pq.offer(order.score);
                totalScore += order.score;
            } else if (!pq.isEmpty() && pq.peek() < order.score) {
                // 如果当前时间大于该工单的 SLA 时间，且该工单的积分大于优先队列中的最小积分
                totalScore -= pq.poll();
                pq.offer(order.score);
                totalScore += order.score;
            }
        }

        // 输出最大积分
        System.out.println(totalScore);
    }
}
